# 树上倍增
snippet bz_lca "树上倍增" b
//============= 树上倍增 BEG
namespace BZ_LCA {
    const int SIZ = 35;
    int f[maxn][SIZ+1],len[maxn][SIZ+1],dep[maxn];
    using namespace xlx1;
    void dfs_init(int u ,int d,int fa,int w){
        dep[u] = d; f[u][0] = fa; len[u][0] = w;
        for(int i= 1;i<=SIZ;++i){
            f[u][i] = f[f[u][i-1]][i-1];
            len[u][i] = len[u][i-1]+len[f[u][i-1]][i-1];
        }
        for(int i=head[u];~i;i=e[i].next){
            int v =e[i].v ,w = e[i].w;
            if( v == fa) continue;
            dfs_init(v,d+1,u,w);
        }
    }
    int find_lca(int u,int v){
        int sum = 0;
        if( dep[u] < dep[v]) swap(u,v); //保证u点的深度深
        for(int i=SIZ;i>=0;--i){
            if( dep[f[u][i]] < dep[v]) continue; //不跳的区域
            sum+=len[u][i];
            u = f[u][i];
        }
        if(u == v) return sum;
        for(int i=SIZ;i>=0;--i){
            if( f[u][i] == f[v][i] ) continue;
            sum+=len[u][i];
            sum+=len[v][i];
            u = f[u][i];
            v = f[v][i];
        }
        return sum+len[u][0]+len[v][0];
    }
}
//============= 树上倍增 END
endsnippet
